|
The Shapley–Folkman lemma is a result in convex geometry with applications in mathematical economics that describes the Minkowski addition of sets in a vector space. ''Minkowski addition'' is defined as the addition of the sets' members: for example, adding the set consisting of the integers zero and one to itself yields the set consisting of zero, one, and two: : + = = . The Shapley–Folkman lemma and related results provide an affirmative answer to the question, "Is the sum of many sets close to being convex?"〔: 〕 A set is defined to be ''convex'' if every line segment joining two of its points is a subset in the set: For example, the solid disk is a convex set but the circle is not, because the line segment joining two distinct points is not a subset of the circle. The Shapley–Folkman lemma suggests that if the number of summed sets exceeds the dimension of the vector space, then their Minkowski sum is approximately convex. The Shapley–Folkman lemma was introduced as a step in the proof of the Shapley–Folkman theorem, which states an upper bound on the distance between the Minkowski sum and its convex hull. The ''convex hull'' of a set ''Q'' is the smallest convex set that contains ''Q''. This distance is zero if and only if the sum is convex. The theorem's bound on the distance depends on the dimension ''D'' and on the shapes of the summand-sets, but ''not'' on the number of summand-sets ''N'', The shapes of a subcollection of only ''D'' summand-sets determine the bound on the distance between the Minkowski ''average'' of ''N'' sets : (''Q''1 + ''Q''2 + ... + ''Q''''N'') and its convex hull. As ''N'' increases to infinity, the bound decreases to zero (for summand-sets of uniformly bounded size).〔 The Shapley–Folkman theorem's upper bound was decreased by Starr's corollary (alternatively, the Shapley–Folkman–Starr theorem). The lemma of Lloyd Shapley and Jon Folkman was first published by the economist Ross M. Starr, who was investigating the existence of economic equilibria while studying with Kenneth Arrow.〔 In his paper, Starr studied a ''convexified'' economy, in which non-convex sets were replaced by their convex hulls; Starr proved that the convexified economy has equilibria that are closely approximated by "quasi-equilibria" of the original economy; moreover, he proved that every quasi-equilibrium has many of the optimal properties of true equilibria, which are proved to exist for convex economies. Following Starr's 1969 paper, the Shapley–Folkman–Starr results have been widely used to show that central results of (convex) economic theory are good approximations to large economies with non-convexities; for example, quasi-equilibria closely approximate equilibria of a convexified economy. "The derivation of these results in general form has been one of the major achievements of postwar economic theory", wrote Roger Guesnerie. The topic of non-convex sets in economics has been studied by many Nobel laureates, besides Lloyd Shapley who won the prize in 2012: Arrow (1972), Robert Aumann (2005), Gérard Debreu (1983), Tjalling Koopmans (1975), Paul Krugman (2008), and Paul Samuelson (1970); the complementary topic of convex sets in economics has been emphasized by these laureates, along with Leonid Hurwicz, Leonid Kantorovich (1975), and Robert Solow (1987). The Shapley–Folkman lemma has applications also in optimization and probability theory. In optimization theory, the Shapley–Folkman lemma has been used to explain the successful solution of minimization problems that are sums of many functions.〔〔 The Shapley–Folkman lemma has also been used in proofs of the "law of averages" for random sets, a theorem that had been proved for only convex sets.〔 ==Introductory example== For example, the subset of the integers is contained in the interval of real numbers (), which is convex. The Shapley–Folkman lemma implies that every point in () is the sum of an integer from and a real number from (). The distance between the convex interval () and the non-convex set equals one-half : 1/2 = |1 − 1/2| = |0 − 1/2| = |2 − 3/2| = |1 − 3/2|. However, the distance between the ''average'' Minkowski sum : 1/2 ( + ) = and its convex hull () is only 1/4, which is half the distance (1/2) between its summand and (). As more sets are added together, the average of their sum "fills out" its convex hull: The maximum distance between the average and its convex hull approaches zero as the average includes more summands.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Shapley–Folkman lemma」の詳細全文を読む スポンサード リンク
|